Codeforces Round #563 Div2 A~D题解

本场链接:Codeforces Round #563
本场的EF题都到了2500/2400的难度,我爬了

A. Ehab Fails to Be Thanos
题目大意:给定一个长度$2n$的序列,问你是否有可能通过重排这个序列,使得他的前$n$个元素的和后$n$个元素的和不一样.如果可以,则额外输出具体方案是什么.

很显然,如果整个序列排序了,则两边的和如果仍然相同,则必然是一个全相同的序列,原问题无解.否则直接输出排序后的结果就可以了.
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
int a[N];
int main()
{
	int n;scanf("%d",&n);
	for(int i = 0;i < 2 * n;++i)	scanf("%d",&a[i]);
	sort(a,a + 2 * n);
	int ok = 1,l = 0,r = 0;
	for(int i = 0;i < n;++i)	l += a[i];
	for(int i = n;i < 2 * n;++i)	r += a[i];
	if(l == r)	puts("-1");
	else 
		for(int i = 0;i < 2 * n;++i)	printf("%d ",a[i]);

	
    return 0;
}

B. Ehab Is an Odd Person
题目大意:给一个长度为$n$序列,对任意的两个位置$i,j$,如果有$a_i + a_j$是奇数,就可以交换$a_i$和$a_j$,问经过若干次的操作之后,可以得到的字典序最小的序列是什么.

显然,如果一个序列只有奇数或者偶数,就一下都换不了,原序列就是最小的序列了.反之,如果既有奇数又有偶数,可以发现,如果拿任意一个偶数作为跳板,就可以任意的交换所有的元素,奇数也是同理.因此如果既有奇数又有偶数,最小字典序的序列就是排序后的序列,直接输出即可.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int a[N],n;

int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
	int odd = 0,even = 0;
	for(int i = 1;i <= n;++i)
	{
		if(a[i] & 1)	odd = 1;
		else even = 1;
	}
	if(odd && even)	sort(a + 1,a + n + 1);
    for(int i = 1;i <= n;++i)	printf("%d ",a[i]);
    return 0;
}

C. Ehab and a Special Coloring Problem
题目大意:已知两个正整数$n$和$k$,对于在$2$到$n$之间的任意$i$,给这个位置一个值$a_i$,要满足如下两个性质:
①对于任意的两个互质的数$i$和$j$,需要满足$a_i \ne a_j$.
②所有$a_i$的最大值应该尽量小.

数据范围:
$2 \leq n \leq 10^5$
$1 \leq a_i \leq n$

这题由于两两互质的条件比较强,而且暴力的判断每对数肯定是不行的.这肯定要另找出路,很容易想到筛质数里的筛法操作,这里也是同理:对于一个质数$p$显然可以把他所有的倍数全部和他染成一个颜色,这个在筛法里套一个循环就可以了.但是怎么确定颜色有哪些呢?其实顺着上面那个思路就可以想到说:对于一个合数,他和一个质数一起一定是互质的,因此每碰到一个质数,就把染色的数字加一,再往后筛.其次如果两个合数互质的话,说明他俩里面没有相同的质因子,也就是说,他俩一定是由两个不同的质数的颜色翻上来的.所以这个方法是正确的.之后还有一步贪心也就非常顺利成章了:对于每个数,肯定只取最小的质因子染过来的色,因为要使整个序列的所有$a_i$的最大值最小,可以发现这个最大值必然只是质数的个数,而且肯定也不能再减少了.
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int primes[N],st[N],cnt;
int col,res[N];
void init()
{
	for(int i = 2;i < N;++i)
	{
		if(!st[i])	
		{
			primes[cnt++] = i;
			++col;
			for(int j = 1;j * i < N;++j)	
				if(res[i * j] == 0)
					res[i * j] = col;
		}
		for(int j = 0;j < cnt && primes[j] * i < N;++j)
		{
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0)	break;
		}
	}
}
int main()
{
	init();
	int n;scanf("%d",&n);
	for(int i = 2;i <= n;++i)	printf("%d ",res[i]);
    return 0;
}

D. Ehab and the Expected XOR Problem
题目大意:给定两个正整数$n$和$x$,构造一个满足如下要求的序列$a$
①所有元素的值$\in [1,2^n)$
②不存在一个子段的异或和是$0$或者$x$
③整个序列$a$的长度要尽量长.
输出长度以及具体方案.
注意:子段的定义是把$a$序列的开头和结尾各删掉一段连续的序列,当然可以不删,剩下的就是子段.

数据范围:
$1 \leq n \leq 18$
$1 \leq x \leq 2^{18}$

直接构造这个序列必然很困难,考虑用异或前缀和的方式曲线救国:
定义异或前缀和序列$b_i = a_i \oplus a_{i-1}$,则原有的$a_i = b_i \oplus b_{i-1}$.
其次,题目里的条件依次可以这样转换:
①$b_i$的值$\in [1,2^n)$,因为异或后的值必然不会超过$2^n$,所以如此还原的$a$序列的值最终也还是属于这个区间的.
②不存在两个相同的$b_i$,以及$b_i = x$或$b_i = 0$.因为整个子段其实就是两个前缀异或和再异或一次的结果,如果两个$b_i$相同,说明这两个夹着的中间子段是$0$,其次不能是$x$,只要没有一个$x$或者$0$就可以满足不存在$x$了.不过由于$b_i \geq 1$ ,所以$0$这个条件可以不显式的写出来.
③尽量把所有满足的全填进去.

我们来考虑一下这个$b$怎么构造的:首先肯定要把$x$和$0$打上标记去掉,其次,对于每一个在$[1,2^n)$这个区间的值$i$,我们都是可以加进去的,但是如果他加进去了,就不能再加$i\oplus x$了,直接标记$i$和$i\oplus x$即可.整个流程也就非常显然了,即遍历整个范围,找到一个没标记的$i$,把他加入序列,再把他和异或$x$的值一起标记掉.最后还原整个$a$序列输出即可.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1 << 19);
int st[N];
int main()
{
	int n,x;scanf("%d%d",&n,&x);
	st[0] = st[x] = 1;
	vector<int> res;
	for(int i = 1;i < (1 << n);++i)
	{
		if(st[i])	continue;	
		res.push_back(i);
		st[i] = 1;
		st[i ^ x] = 1;
	}
	for(int i = res.size() - 1;i >= 1;--i)	res[i] = res[i] ^ res[i - 1];
	printf("%d\n",res.size());
	for(int i = 0;i < res.size();++i)
		printf("%d ",res[i]);
    return 0;
}